#include "classical-problems.h"
#include <stdlib.h>

namespace pot {

int gcd_(int a, int b) {
  if (b == 0) return a;
  return gcd_(b, a % b);
}

int gcd(int a, int b) {
  if (a > b) return gcd_(a, b);
  else return gcd_(b, a);
}

int gcd_stein(int a, int b) {
  if (a == 0) return b;
  if (b == 0) return a;
  int i, j;
  for (i = 0; 0 == (a & 1); ++i) a >>= 1;
  for (j = 0; 0 == (b & 1); ++j) b >>= 1;
  if (j < i) i = j;
  while (true) {
    if (a < b) {
      int tmp = a;
      a = b;
      b = tmp;
    }
    a -= b;
    if (0 == a) return b << i;
    while (0 == (a & 1)) a >>= 1;
  }
  return 0;
}

void GcdTest() {
  for (int i = 0; i < 1000; ++i) {
    int a = rand();
    int b = rand();
    int d1 = gcd(a, b);
    int d2 = gcd_stein(a, b);
    if (d1 != d2) {
      printf("%d, %d\n", d1, d2);
    }
  }
}
} // pot
